package 代码记录.Bit48天集训;

import java.util.Scanner;

/**答案已订正
 * 1.另类加法
 * 2.走方格的方案数(最简单的动态规划)
 * @author zx
 * @create 2022-04-26 20:25
 * 暴露的问题：位运算相关的题目和动态规划还是不太行
 */
public class day_09 {
    /**
     * 二进制加法。发现一个特点。
     * 位的异或运算跟求'和'的结果一致：(不考虑进位)
     * 异或 1^1 = 0 1^0 = 1 0^0 = 0
     * 求和 1+1 = 0 1+0 = 1 0+0 = 0
     * 位的与运算跟求'进位'的结果一致：(只考虑进位)
     * 位与 1&1 = 1 1&0 = 0 0&0 = 0
     * 进位 1+1 = 1 1+0 = 0 0+0 = 0
     * 于是可以用异或运算和与运算来表示加法
     * @return
     * sum存放异或的结果,未进位的异或;
     * jin存放进位结果,通过位移操作
     */
    public int addAB(int A, int B) {
        int sum, jin;
        while (B != 0) {
            sum = A ^ B;
            jin = (A & B) << 1;
            A = sum;
            B = jin;
        }
        return A;
    }

    /**
     * 人家好的做法
     */
    public static void main(String ... args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNextInt()){
            // n个格子就有n + 1条线
            int n = sc.nextInt() + 1, m = sc.nextInt() + 1;
            // 避免处理边界问题（实际上空间消耗增加了）
            int[][] d = new int[n + 1][m + 1];
            // 初始子问题：只有一个点时有一条路，其他时候都为它上面的路和加左边的路和
            d[1][1] = 1;
            for(int i = 1; i <= n; i++){
                for(int j = 1; j <= m; j++){
                    d[i][j] += d[i - 1][j] + d[i][j - 1];
                }
            }
            System.out.println(d[n][m]);
        }
    }
}
